package ljl.codetop300;

public class _63_diff_routes {

  /**
   * 就一个解法，dp
   */
  static class test {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      int m = obstacleGrid.length;
      int n = obstacleGrid[0].length;
      int[][] dp = new int[m][n];
      for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        dp[i][0] = 1;
      }
      for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
        dp[0][i] = 1;
      }
      for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
          if (obstacleGrid[i][j] == 0) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
          }
        }
      }
      return dp[m - 1][n - 1];
    }
  }

  /**
   * 敌人技高一筹
   * 一维的貌似更难理解，真的是这样吗
   * 你能让自己搞懂，那你才是真懂
   */
  static class off {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      // 草泥马为什么是 n m 而不是 m n
      int n = obstacleGrid.length, m = obstacleGrid[0].length;
      int[] f = new int[m];
      f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          if (obstacleGrid[i][j] == 1) {
            f[j] = 0;
          } else if (j > 0 && obstacleGrid[i][j - 1] == 0) {
            f[j] += f[j - 1];
          }
        }
      }
      return f[m - 1];
    }
  }

  static class copyoff {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      int m = obstacleGrid.length;
      int n = obstacleGrid[0].length;
      int[] dp = new int[n];
      if (obstacleGrid[0][0] == 0) dp[0] = 1;
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
          if (obstacleGrid[i][j] == 1) {
            dp[j] = 0;
          } else if (j > 0 && obstacleGrid[i][j - 1] == 0) {
            dp[j] += dp[j - 1];
          }
        }
      }
      return dp[n - 1];
    }
  }
}
